551,回溯算法解分割回文串
I think a man does what he can until his destiny is revealed to him.
一个人应该竭尽所能,然后才听天由命。
问题描述
来源:LeetCode第131题
难度:中等
给你一个字符串s,请你将s分割成一些子串,使每个子串都是回文串。返回s所有可能的分割方案。
回文串是正着读和反着读都一样的字符串。
示例 1:
输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
示例 2:
输入:s = "a"
输出:[["a"]]
提示:
1 <= s.length <= 16
s 仅由小写英文字母组成
回溯算法解决
这题让把字符串分隔成多个子串,并且每个子串都是回文的,问有多少种分隔方案。这里就以示例1为例来看下怎么分隔,字符串aab
截取1位a,把剩下的ab当做一个新的字符串再继续判断……
截取2位aa,把剩下的b当做一个新的字符串再继续判断……
截取3位aab,已经截取完了。
具体截取来看下图
来看下视频演示
一看就知道,其实就是个n叉树的DFS遍历,从根节点到叶子节点是字符串s截取的子串,我们只需要判断这些子串是否都是回文串即可,只要有一个不是就可以直接终止,如果从根节点到叶子节点的每个子串都是回文串,说明我们找到了一组截取方案。
但这题让把截取的结果返回,所以我们很容易想到的就是使用回溯算法解决,关于回溯算法不明白的可以看下《450,什么叫回溯算法,一看就会,一写就废》,大致代码如下
1/**
2 * @param s 就是需要截取的字符串
3 * @param index 字符串开始截取的位置
4 * @param res 最终的分隔方案结果
5 * @param cur 沿着当前分支截取的子串
6 */
7public void backTrack(String s, int index, List<List<String>> res, List<String> cur) {
8 //边界条件判断,如果字符串s中的字符都访问完了(类似于到叶子节点了),就停止查找,
9 //然后这个分支的所有元素加入到集合res中
10 if (index >= s.length()) {
11 res.add(new ArrayList<>(cur));
12 return;
13 }
14
15 for (int i = index; i < s.length(); i++) {
16 //如果当前截取的子串不是回文的,就跳过
17 if (!isPalindrome(s, index, i))
18 continue;
19 //做出选择,开始截取,把截取的子串放到集合cur中
20 cur.add(s.substring(index, i + 1));
21 //递归,到下一层(类似于到n叉树的子节点去遍历)
22 backTrack(s, i + 1, res, cur);
23 //撤销选择,就是把之前截取放到集合cur中的子串给移除掉
24 cur.remove(cur.size() - 1);
25 }
26}
搞懂了上面的分析过程,我们再来看下最终代码
1public List<List<String>> partition(String s) {
2 //最终要返回的结果
3 List<List<String>> res = new ArrayList<>();
4 backTrack(s, 0, res, new ArrayList<>());
5 return res;
6}
7
8public void backTrack(String s, int index, List<List<String>> res, List<String> cur) {
9 //边界条件判断,如果字符串s中的字符都访问完了(类似于到叶子节点了),就停止查找,
10 //然后这个分支的所有元素加入到集合res中
11 if (index >= s.length()) {
12 res.add(new ArrayList<>(cur));
13 return;
14 }
15 for (int i = index; i < s.length(); i++) {
16 //如果当前截取的子串不是回文的,就跳过
17 if (!isPalindrome(s, index, i))
18 continue;
19 //做出选择
20 cur.add(s.substring(index, i + 1));
21 //递归
22 backTrack(s, i + 1, res, cur);
23 //撤销选择
24 cur.remove(cur.size() - 1);
25 }
26}
27
28//判断字符串从[left,right]的子串是否是回文的
29public boolean isPalindrome(String str, int left, int right) {
30 while (left < right) {
31 if (str.charAt(left++) != str.charAt(right--))
32 return false;
33 }
34 return true;
35}
回溯算法代码优化
上面每次截取的时候都要判断截取的子串是否是回文的,实际上我们还可以先判断字符串s中所有的子串哪些是回文的哪些不是,然后计算的时候直接使用就可以了。这里使用一个二维数组dp,其中dp[i][j]表示字符串从下标i到j构成的子串是否是回文的,看下代码
1 //数组dp[i][j]表示字符串s下标[i,j]的子串是否是回文的
2 boolean[][] dp = new boolean[length][length];
3 for (int i = 0; i < length; i++) {
4 for (int j = 0; j <= i; j++) {
5 if (s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j + 1][i - 1])) {
6 dp[j][i] = true;
7 }
8 }
9 }
10
不懂的可以看下《540,动态规划和中心扩散法解回文子串》,这里就不在重复介绍
再来看下最终代码
1public List<List<String>> partition(String s) {
2 //最终要返回的结果
3 List<List<String>> res = new ArrayList<>();
4 int length = s.length();
5
6 //下面先计算子串中哪些是回文的,哪些不是
7 //数组dp[i][j]表示字符串s下标[i,j]的子串是否是回文的
8 boolean[][] dp = new boolean[length][length];
9 for (int i = 0; i < length; i++) {
10 for (int j = 0; j <= i; j++) {
11 if (s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j + 1][i - 1])) {
12 dp[j][i] = true;
13 }
14 }
15 }
16 backTrack(s, dp, 0, res, new ArrayList<>());
17 return res;
18}
19
20public void backTrack(String s, boolean[][] dp, int index, List<List<String>> res, List<String> cur) {
21 //边界条件判断,如果字符串s中的字符都访问完了(类似于到叶子节点了),就停止查找,
22 //然后这个分支的所有元素加入到集合res中
23 if (index >= s.length()) {
24 res.add(new ArrayList<>(cur));
25 return;
26 }
27 for (int i = index; i < s.length(); i++) {
28 //如果当前截取的子串不是回文的,就跳过
29 if (!dp[index][i])
30 continue;
31 //做出选择
32 cur.add(s.substring(index, i + 1));
33 //递归
34 backTrack(s, dp, i + 1, res, cur);
35 //撤销选择
36 cur.remove(cur.size() - 1);
37 }
38}
总结
回溯算法其实是有一个经典的模板的,掌握这个模板,很多关于回溯算法的题套用模板然后稍加修改基本上都能解决,关于模板可以看下《450,什么叫回溯算法,一看就会,一写就废》,总结一下就是3步
做出选择
递归到下一层
撤销选择
截止到目前我已经写了500多道算法题了,为了方便大家阅读,我把部分算法题整理成了pdf文档,目前有1000多页,大家可以在公众号中回复关键字“pdf”即可获取下载链接。